10271. АДА школа

В классе ADA School расположены n ⋅ m парт в виде прямоугольной сетки из n строк и m столбцов. Каждая парта занята ровно одним учеником.

Перед началом занятия учитель решил немного перетасовать учеников. После перетасовки каждый стол снова должен быть занят ровно одним учеником. Кроме того, каждый учащийся должен занять стол, примыкающий к его исходному столу, то есть находящийся непосредственно слева, справа, вверху или внизу этого стола.

Могут ли ученики переставить парты при соблюдении всех условий учителя?

Вход. Первая строка содержит количество тестов t. Каждая из следующих t строк содержит два целых числа n и m (2 ≤ n, m ≤ 1000).

Выход. Для каждого теста выведите строку “YES” если можно выполнить условия учителя и “NO” иначе.

Sample input	Sample ouutput
2 5 5 4 4	NO YES

РЕШЕНИЕ

математика

Анализ алгоритма

Рассмотрим случай, когда одна из размерностей сетки четная. Пусть, например, n (количество строк) четно. Тогда перестановку парт можно совершить следующим образом:

Если n и m нечтные, то перестановки не существует. Раскрасим клетки сетки в белый и черный цвет в шахматном порядке. При перемещении парта, которая стояла на черной клетке, должна переместиться на белую и наоборот. Для возможности перестановки всех парт количетво белых и черных клеток должно быть одинаковым, а следовательно общее количество парт должно быть четным. При нечетных n и m количество парт n ⋅ m является нечетным числом.

Реализация алгоритма

Читаем количество тестов t.

scanf("%d", &t);

while (t--)

{

Читаем входные данные каждого теста.

scanf("%d %d", &n, &m);

Если n и m нечетные, то ответ “NO”.

if (n % 2 == 1 && m % 2 == 1)

puts("NO");

Иначе ответ “YES”.

else

puts("YES");

}